package Algorithm.dynamicProgramming.introduct;

/**
 * 63. 不同路径 II https://leetcode.cn/problems/unique-paths-ii
 * 题目简述：一个机器人位于一个m x n网格的左上角。机器人每次只能向下或者向右移动一步。有些网格中有障碍物（网格值为1）不能走，机器人到达网格的右下角总共有多少条不同的路径？
 */
public class UniquePathsWithObstacles {

    public static void main(String[] args) {
        new UniquePathsWithObstacles().uniquePathsWithObstacles(new int[][]{{1,0}});
    }

    /**
     * 动态规划
     * 1. 定义dp：dp[i][j]为到达坐标(i,j)的格子的路径数
     * 2. 确定递推公式：若格子(i,j)有障碍物，dp[i][j]=0。若格子(i,j)为空位置，则只能由上方的格子(i-1,j)或者左边的格子(i,j-1)走来，故dp[i][j] = dp[i-1][j] + dp[i][j-1]
     * 3. 初始化dp: 第一行和第一列在第一个障碍物之前的格子的路径数均为1，障碍物后的格子的路径数均为0
     * 4. 遍历方式：从(1, 1)开始从上往下逐行遍历
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        //m行，一行n个格子
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for(int i=0;i < m && obstacleGrid[i][0] == 0;i++) {
            dp[i][0] = 1;
        }
        //注意这里要从0开始
        for(int j=0;j < n && obstacleGrid[0][j] == 0;j++) {
            dp[0][j] = 1;
        }
        for(int i=1;i < m;i++) {
            for(int j=1;j < n;j++) {
                if(obstacleGrid[i][j] == 0)
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}
